package base

//基数排序
/**
	规则：
		 1.获取最大位数s（如果已知最大位数忽略）
		 2.从n位开始进行计数排序
		 3.n+1 重复第二步 直到n等于s
**/

import "math"

//Sort v or int array
func Sort(v []int) {
	// var count [10]int
	conut := make([]int, 10)
	sl := 0
	sli := 0
	for i := 0; i < len(v); i++ { //获取最位数
		sli = several(v[i])
		if sli > sl {
			sl = sli
		}
	}

	for i := 1; i <= sl; i++ {
		copy(v, counting(v, conut, i)) //进行计数排序
	}

}

//计数排序
/**
	规则：
		 1.建立计数器count  计数器容量为数据最大值+1 （这里是服从基数排序的 十进制位数最大值是9  所以容量是10）
		 2.重置计数器count
		 3.记录每个数字有多少   如（1,1,5,9,8） 计数器内（0,2,0,0,0,1,0,0,1,1）
		 4.计算每个数字小于等于它的有多少   如（1,1,5,9,8） 计数器内（0,2,0,0,0,1,0,0,1,1）->(0,2,2,2,2,3,3,3,4,5)  更具这个发现 1小于等于它的有2个  9小于等于它的有5个
		 5.开始填充新数组更具计数器内已知小于等于该数有多少个进行安排位置  如 9 已知大于等于9有5个  所以可以吧9安排至 新数组下标（5-1）4位置中
**/
func counting(v []int, count []int, dt int) []int {

	cont := make([]int, len(v)) //建立排序后容器

	for i := 0; i < len(count); i++ { //重置计数器
		count[i] = 0
	}

	for i := 0; i < len(v); i++ { //记录每个数字有多少
		count[digit(v[i], dt)]++
	}

	for i := 1; i < len(count); i++ { //计算每个数字小于等于它的有多少
		count[i] += count[i-1]
	}

	vi := 0
	for i := len(v) - 1; i >= 0; i-- { //开始填充新数组
		vi = digit(v[i], dt)
		cont[count[vi]-1] = v[i]
		count[vi]--
	}
	return cont
}

/**
	num 数字
	dig 位数
	return num数字第dig位的数字
**/
func digit(num, dig int) int {
	dig--
	num /= int(math.Pow(10, float64(dig)))
	return num % 10
}

/**
	num 数字
	return 数字有几位
**/
func several(num int) int {
	several := 0
	for num > 0 {
		several++
		num /= 10
	}
	return several
}
